Whenever information is transferred across a bus or other communication lines, there is the possibility that data may be corrupted. Therefore it is desirable to detect and even correct errors that occur in transmission. In the prior art, Hamming codes are used to correct single bit errors in transmission. This is done by the utilization of parity bits. For a general discussion on the use of parity bits and Hamming codes see Richard E. Blahut, Theory and Practice of Error Control Codes, Edison Wesley, 1983, pp. 11-12, 54-55.
Under the traditional method, for every "n" bits of data, there are required "m" Hamming parity bits. The formula for calculating m is the following: EQU m=1n.sub.2 (n)+1
In addition to single bit error correction, double bit error detection may be achieved by adding a sngle overall parity bit. Therefore, for one-bit error correction and two-bit error detection m+1 parity bits need to be used for every n data bits.
For example, if data is being transferred in sixty-four bit words, for every sixty-four (n) bit words of data, seven (m) parity bits must be added in order to correct one-bit errors. m is calculated from the above formula. In order to detect two-bit errors an eighth parity bit must be added.
Table 1, in FIG. 1, is used to illustrate the implementation of a traditional hamming algorithm. In this implementation, sixty-four bits of information and eight parity bits are used. Each column in Table 1 represents a single line on which is placed a single data bit or a single parity bit. Parity bits are sometimes referred to as code bits, as explained further below.
Row 1 contains letters designating whether each line contains a data bit or a parity bit. If the letter is a "B", the line contains a data bit. If the letter is a "C", the line contains a parity bit. Row 2 and Row 3 number the lines. The parity bits are numbered from 0 to 7. The data bits are numbered from 0 to 63. The parity bits are referred to as C0-C7. The data bits are referred to as B0-B63.
As will be explained in greater detail in the Description of the Preferred Embodiment below, lines containing the data bits and the parity bits are coupled into logic circuitry to generate bits P0-P7, shown in column 13. Bits P0-P7 may be code bits or syndrome bits, as further described below. In this discussion, bits P0-P7 will be assumed to be syndrome bits.
Syndrome bits P0-P7 are used to detect and correct errors. The information in Rows 4-11 show which data bits and which parity bits are used to calculate each of the syndrome bits P0-P7. A "1" in the row indicates that a data bit or parity bit is used to calculate the corresponding syndrome bit in Column 13. A "0" in the row indicates that a data bit or parity bit is not used to calculate the corresponding syndrome bit in column 13. For instance, all eight parity bits and all sixty-four data bits are used to generate syndrome bit P0. On the other hand only parity bit C7 and data bits B57, B58, B59, B60, B61, B62 and B63 are used to generate syndrome bit P7.
Column 14 shows the total number of data bits and parity bits to generate each syndrome bit P0-P7. As can be seem, 72 parity bits and data bits are used to generate syndrome bit P0. 36 parity bits and data bits are used to generate syndrome bit P1. 36 parity bits and data bits are used to generate syndrome bit P2. 36 parity bits and data bits are used to generate syndrome bit P3. 32 parity bits and data bits are used to generate syndrome bit P4. 32 parity bits and data bits are used to generate syndrome bit P5. 32 parity bits and data bits are used to generate syndrome bit P6. 8 parity bits and data bits are used to generate syndrome bit P7.
Row 12 shows how many times each parity bit C0-C7 and each data bit B0-B63 is used to calculate one of the syndrome bits P0-P7. As can be seen, the values range from 1 to 7. That is parity bit CO is used in the calculation of only one syndrome bit--syndrome bit P0--, while data bit B56 is used in the calculation of seven syndrome bits--all but syndrome bit P7--.
The time required to generate each syndrome bit is relative to the number of data bits B0-B63 and parity bits C0-C7 used to generate that syndrome bit. This is because, the larger the number of inputs, the more levels of logic must be utilized to generate an output.
Syndrome bit P0 is used as an overall parity bit. In the prior art an overall parity bit has been required for double error detection. 72 data and parity bits are required to generate syndrome bit P0; therefore, in the prior art, in order to perform double error detection, the critical path has been the determination of the overall parity bit, requiring at least one more layer of logic than is required to calculate any of the other syndrome bits P1-P7. In order to avoid the additional delay, some prior art system, do not have an overall parity bit. That is, in the embodiment shown in FIG. 1, syndrome bit P0 would be omitted and double error detection would not be performed.
Similarly, the number of times each parity bit C0-C7 and each data bit B0-B63 is used to calculate one of the syndrome bits P0-P7 has a notable effect on performance. This is because each input of the circuitry which generates syndrome bits P0-P7 has a certain amount of capacitance that must be overcome. If a single parity bit or a single data bit issued in the generation of many syndrome bits additional time has to be allowed for the overcoming of the input capacitance.
As may be understood from the preceding discussion, the prior art implementations of hamming algorithms for error correction and detection have not been optimal. The wide variance in the total number of data and parity bits to generate each syndrome bit, and the varying number of times each parity bit and data bit are used to generate a syndrome bit have degraded the performance of these prior art systems. It is an objective of the present invention to present an apparatus which overcome the stated defects of the prior art systems.